[Coding019] Sort - 插入排序

希尔排序

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：希尔排序

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

思想

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。

• 这样可以让一个元素可以一次性地朝最终位置前进一大步。

• 然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

C语言代码实现

​x
1
#include<stdio.h>
2

3
void ShellSort(int* array, int length)
4
{
5
    int d = length / 2;
6
    int i;
7
    int j;
8
    int temp;
9
    
10
    while(d > 0)
11
    {
12
        // i 从 第一跨的最后一个元素 -> 最后一个元素 
13
        for(i = d; i < length; i++)
14
        {
15
            // 当前元素，向前propagate
16
            temp = array[i];
17
            j = i - d;
18
            
19
            // 如果当前跨向前还有元素（索引不是负数）， 并且跨前元素大于跨后元素，exchange them 
20
            while(j >= 0 && array[j] > temp)
21
            {
22
                // temp <- array[i]
23
                // array[i] <- array[j]
24
                // array[j] <- temp 
25
                array[i] = array[j];
26
                array[j] = temp;
27
                
28
                // propagate
29
                i = j;
30
                j = i - d;
31
                
32
                // temp <- 当前位置的数值（为了下一次循环判断） 
33
                temp = array[i];
34
            }
35
        }
36
        d = d / 2; 
37
    }
38
    
39
}
40

41

42
int main()
43
{
44
    int length;
45
    int array[100];
46
    
47
    int i;
48
    
49
    scanf("%d", &length);
50
    
51
    for(i = 0; i < length; i++)
52
    {
53
        scanf("%d", &array[i]);
54
    }
55
    ShellSort(array, length);
56
    
57
    for(i = 0; i < length; i++)
58
    {
59
        printf("%d ", array[i]);
60
    }
61
    printf("\n");
62
    return 0;
63
}
64

65
/*
66

67
10
68
9 3 1 2 5 4 6 8 7 0
69

70
10
71
46 32 13 24 10 91 67 88 79 55
72

73
5
74
1 4 3 5 2
75

76
5
77
3 3 1 4 2
78

79
3
80
3 3 1
81

82
2
83
4 1
84

85
*/

运行结果

Java语言代码实现

xxxxxxxxxx
121
1
import java.util.Scanner;
2

3
// 这是一个类，名叫Solution
4
public class Solution {
5

6
    /**
7
     * 希尔插入排序(shell Insert Sort)
8
     */
9
    
10
    public static void main(String[] args) {
11
        // TODO Auto-generated method stub
12
        System.out.println("Hello, T!");
13
        
14
        Scanner input = new Scanner(System.in);
15
        
16
        int n = input.nextInt();
17
        
18
        int[] arr = new int[n];
19
        int[] arr2 = new int[n];
20
        for (int i = 0; i < n; i++)
21
        {
22
            arr[i] = input.nextInt();
23
            arr2[i] = arr[i];
24
        }
25
        
26
        for(int e : arr){
27
            System.out.print(e + " ");
28
        }
29
        System.out.println("\n--------------");
30
        
31
        Solution sol = new Solution();  
32
        System.out.println("Shell01:\n");
33
        sol.insertSort_shell01(arr, arr.length);
34
        System.out.println("Shell02:\n");
35
        sol.insertSort_shell02(arr2, arr2.length);
36
        
37
        for(int e : arr){
38
            System.out.print(e + " ");
39
        }
40
        return;
41
    }
42

43
    public void insertSort_shell01(int[] arr, int n)
44
    {       
45
        int d = n / 2;
46
        while(d > 0)
47
        {
48
            // 这里需要注意，i从d开始，往后加！
49
            for(int i = d; i < n; i++)
50
            {
51
                int x = arr[i];
52
                int j = i - d;  // 这里需要注意，j从i-d开始，往前跑：propagate！（不管是直接插入排序还是shell插入排序，都需要一个j，这个j是慢慢往前跑的）
53
                while(j >= 0 && x < arr[j])
54
                {
55
                    arr[j + d] = arr[j];
56
                    j = j - d;
57
                }
58
                arr[j + d] = x;
59
            }
60
            System.out.println("01---------");
61
            for(int k = 0; k < n; k++)
62
            {
63
                System.out.print(arr[k] + " ");
64
            }
65
            System.out.println();
66
            d = d / 2;
67
        }
68
    }
69
    
70
    public void insertSort_shell02(int[] arr, int n)
71
    {       
72
        int d = n / 2;
73
        while(d > 0)
74
        {
75
            for(int i = d; i < n; i++)
76
            {
77
                int x = arr[i];
78
                int j = i - d;
79
                while(j >= 0 && x < arr[j])
80
                {
81
                    arr[i] = arr[j];
82
                    arr[j] = x;
83
                    
84
                    i = j;
85
                    j = i - d;
86
                    
87
                    x = arr[i];
88
                }
89
            }
90

91
            System.out.println("02---------");
92
            for(int k = 0; k < n; k++)
93
            {
94
                System.out.print(arr[k] + " ");
95
            }
96
            System.out.println();
97
            d = d / 2;
98
        }
99
    }
100

101
}
102

103
/*
104
测试样例:
105
5
106
5 4 7 9 6
107

108
9
109
65 70 75 80 85 60 55 50 45
110

111
10
112
10 20 30 40 50 60 70 80 90 100
113

114
20
115
12 54 63 54 87 52 49 32 65 48 90 27 30 65 3 9 6 14 18 0
116

117
10
118
46 32 13 24 10 91 67 88 79 55
119

120
*/

运行结果

重点代码段解读

Test Case: 91 32 13 24 55 46 67 88 79 10

• d=5时，只调换1次；

• d = d / 2; → d = 2，此时会出现自后向前传递式调换；

关于希尔排序的稳定性